//每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成
//了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 
//是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。 
//
// 在结果列表中，选择 字典序最小 的名字作为真实名字。 
//
// 
//
// 示例： 
//
// 
//输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], 
//synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
//输出：["John(27)","Chris(36)"] 
//
// 
//
// 提示： 
//
// 
// names.length <= 100000 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 哈希表 字符串 计数 👍 77 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-09-12 22:21:28
 * @description 面试题 17.07.婴儿名字
 */
public class BabyNamesLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 BabyNamesLcci fun=new BabyNamesLcci();
	 	 Solution solution = fun.new Solution();
		  String[] names = {"John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"};
		  String[] synonyms = {"(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"};
		solution.trulyMostPopular(names,synonyms);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)


	public class Solution {
		public String[] trulyMostPopular1(String[] names, String[] synonyms) {
			UnionFind uf = new UnionFind();

			// 首先处理所有名字，包括提取频率
			for (String name : names) {
				int leftBracket = name.indexOf('(');
				int rightBracket = name.indexOf(')');
				String realName = name.substring(0, leftBracket);
				int frequency = Integer.parseInt(name.substring(leftBracket + 1, rightBracket));
				uf.addName(realName, frequency);
			}

			// 处理同义词
			for (String synonym : synonyms) {
				String[] namesInSynonym = synonym.substring(1, synonym.length() - 1).split(",");
				String name1 = namesInSynonym[0];
				String name2 = namesInSynonym[1];
				uf.union(name1, name2);
			}

			// 收集结果
			Map<String, Integer> resultMap = new HashMap<>();
			for (String name : uf.parent.keySet()) {
				String root = uf.find(name);
				if (!resultMap.containsKey(root)) {
					resultMap.put(root, uf.frequency.get(root));
				}
			}

			// 转换为数组
			String[] res = new String[resultMap.size()];
			int index = 0;
			for (Map.Entry<String, Integer> entry : resultMap.entrySet()) {
				res[index++] = entry.getKey() + "(" + entry.getValue() + ")";
			}

			return res;
		}

		class UnionFind {
			Map<String, String> parent;
			Map<String, Integer> frequency;
			Map<String, Integer> rank;

			public UnionFind() {
				parent = new HashMap<>();
				frequency = new HashMap<>();
				rank = new HashMap<>();
			}

			public void addName(String name, int freq) {
				if (!parent.containsKey(name)) {
					parent.put(name, name);
					frequency.put(name, freq);
					rank.put(name, 0);
				} else {
					frequency.put(name, frequency.get(name) + freq);
				}
			}

			public String find(String x) {
				if (!parent.containsKey(x)) {
					addName(x, 0); // 如果名字不存在，先添加
				}

				if (!parent.get(x).equals(x)) {
					parent.put(x, find(parent.get(x))); // 路径压缩
				}
				return parent.get(x);
			}

			public void union(String x, String y) {
				// 确保两个名字都存在
				if (!parent.containsKey(x)) addName(x, 0);
				if (!parent.containsKey(y)) addName(y, 0);

				String rootX = find(x);
				String rootY = find(y);

				if (rootX.equals(rootY)) return;

				// 总是让字典序较小的作为根
				if (rootX.compareTo(rootY) < 0) {
					parent.put(rootY, rootX);
					frequency.put(rootX, frequency.get(rootX) + frequency.get(rootY));
				} else {
					parent.put(rootX, rootY);
					frequency.put(rootY, frequency.get(rootX) + frequency.get(rootY));
				}
			}
		}
		public String[] trulyMostPopular(String[] names, String[] synonyms) {
			Map<String, Integer> map = new HashMap<>();
			Map<String, String> unionMap = new HashMap<>();     //并查集， key(子孙)->value(祖宗)
			for (String name : names) {     //统计频率
				int idx1 = name.indexOf('(');
				int idx2 = name.indexOf(')');
				int frequency = Integer.valueOf(name.substring(idx1 + 1, idx2));
				map.put(name.substring(0, idx1), frequency);
			}
			for (String pair : synonyms) {  //union同义词
				int idx = pair.indexOf(',');
				String name1 = pair.substring(1, idx);
				String name2 = pair.substring(idx + 1, pair.length() - 1);
				while (unionMap.containsKey(name1)) {   //找name1祖宗
					name1 = unionMap.get(name1);
				}
				while (unionMap.containsKey(name2)) {   //找name2祖宗
					name2 = unionMap.get(name2);
				}
				if(!name1.equals(name2)){   //祖宗不同，要合并
					int frequency = map.getOrDefault(name1, 0) + map.getOrDefault(name2, 0);    //出现次数是两者之和
					String trulyName = name1.compareTo(name2) < 0 ? name1 : name2;
					String nickName = name1.compareTo(name2) < 0 ? name2 : name1;
					unionMap.put(nickName, trulyName);      //小名作为大名的分支，即大名是小名的祖宗
					map.remove(nickName);       //更新一下数据
					map.put(trulyName, frequency);
				}
			}
			String[] res = new String[map.size()];
			int index = 0;
			for (String name : map.keySet()) {
				StringBuilder sb = new StringBuilder(name);
				sb.append('(');
				sb.append(map.get(name));
				sb.append(')');
				res[index++] = sb.toString();
			}
			return res;
		}


	}
//leetcode submit region end(Prohibit modification and deletion)

}
